package arithmeticSortList2;

//import com.sun.javafx.sg.prism.web.NGWebView;

/**
 * 二分查找又称折半查找，它是一种效率较高的查找方法。 
 * 。二分查找中查找点计算如下：
　　mid=(low+high)/2, 即mid=low+1/2*(high-low);
 * 
 * 【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
 * 
   * 　注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。
 * 但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》
 * 
 * @author zybw-kf01
 *
 */
public class BinarySearch {
	public static void main(String[] args) {
		int [] nums=new int [20];
		for (int i = 0; i < nums.length; i++) {
			nums[i]=i*2;
		}
		System.out.println(binarySearch(nums, 30));
		System.out.println("BinarySearch2=="+BinarySearch2(nums, 30, 0,nums.length-1));
	}

	/** 
	 *  //二分查找（折半查找-非递归） 
	 * @param array 
	 *            有序数组 * 
	 * @param searchKey 
	 *            查找元素 * 
	 * @return searchKey的数组下标，没找到返回-1 
	 */
	public static int binarySearch(int[] array, int searchKey) {

		int low = 0;
		int high = array.length - 1;
		while (low <= high) {
			int middle = (low + high) / 2;
			if (searchKey == array[middle]) {
				return middle;
			} else if (searchKey < array[middle]) {
				high = middle - 1;
			} else {
				low = middle + 1;
			}
		}
		return -1;
	}
	
	//二分查找，递归  
	public static int BinarySearch2(int a[], int value, int low, int high)  {  
	    int mid = low+(high-low)/2;  
	    if(a[mid]==value)  
	        return mid;  
	    if(a[mid]>value)  
	        return BinarySearch2(a, value, low, mid-1);  
	    if(a[mid]<value)  
	        return BinarySearch2(a, value, mid+1, high);  
	    return -1;
	}  
}
